// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef __HIERARCHICALGRID_H_INCLUDED__
#define __HIERARCHICALGRID_H_INCLUDED__

#include "IO/DataStream/DataStream.h"

template<typename T, T EmptyValue>
class HierarchicalGridNode
{
public:
	enum EType
	{
		k_typeNull = 0,
		k_typeGrid,
		k_typeQuad,
	};

public:
	HierarchicalGridNode()
	{
	}

	virtual ~HierarchicalGridNode()
	{
	}

	virtual s32 GetType() const = 0;
	virtual T Get(s32 x, s32 y) const = 0;
	virtual void Export(DataStream& stream) const = 0;
};

template<typename T, T EmptyValue>
class HierarchicalGridNode_Grid : public HierarchicalGridNode<T,EmptyValue>
{
public:
	HierarchicalGridNode_Grid(T* data, s32 stride, s32 sx, s32 sy) :
		HierarchicalGridNode<T,EmptyValue>(),
		m_sx(sx),
		m_sy(sy),
		m_grid(0)
	{
		m_grid = NEW T[m_sx*m_sy];
		for(s32 y = 0; y < m_sy; ++y)
		{
			for(s32 x = 0; x < m_sx; ++x)
			{
				m_grid[y*m_sx + x] = data[y*stride + x];
			}
		}
	}

	virtual ~HierarchicalGridNode_Grid()
	{
		SAFE_DEL_ARRAY(m_grid);
	}

	virtual s32 GetType() const
	{
		return HierarchicalGridNode<T,EmptyValue>::k_typeGrid;
	}

	virtual T Get(s32 x, s32 y) const
	{
		ASSERT(0 <= x && x < m_sx);
		ASSERT(0 <= y && y < m_sy);
		return m_grid[y*m_sx + x];
	}

	HierarchicalGridNode_Grid(DataStream& stream) :
		HierarchicalGridNode<T,EmptyValue>(),
		m_sx(-1),
		m_sy(-1),
		m_grid(0)
	{
		m_sx = stream.ReadShort();
		m_sy = stream.ReadShort();
		m_grid = NEW T[m_sx*m_sy];
		stream.Read(m_grid, m_sx*m_sy*sizeof(T));
	}

	virtual void Export(DataStream& stream) const
	{
		stream.WriteShort(m_sx);
		stream.WriteShort(m_sy);
		stream.Write(m_grid, m_sx*m_sy*sizeof(T));
	}

	s16 m_sx;
	s16 m_sy;
	T* m_grid;
};


template<typename T, T EmptyValue>
class HierarchicalGridNode_Quad : public HierarchicalGridNode<T,EmptyValue>
{
public:
	enum EScanResult
	{
		k_empty = 0,
		k_mixed,
		k_full,
	};
public:
	HierarchicalGridNode_Quad(T* data, s32 stride, s32 sx, s32 sy) :
		HierarchicalGridNode<T,EmptyValue>(),
		m_sx0(sx / 2),
		m_sy0(sy / 2)
	{
		s32 sxs[2];
		s32 sys[2];
		sxs[0] = m_sx0;
		sxs[1] = sx - m_sx0;
		sys[0] = m_sy0;
		sys[1] = sy - m_sy0;

		for(s32 j = 0; j < 2; ++j)
		{
			for(s32 i = 0; i < 2; ++i)
			{
				s32 x = i * m_sx0;
				s32 y = j * m_sy0;
				HierarchicalGridNode<T,EmptyValue>* node;
				if (sxs[i] && sys[j])
				{
					node = CreateNode(data + y*stride + x, stride, sxs[i], sys[j]);
				}
				else
				{
					node = 0;
				}
				nodes[j*2 + i] = node;
			}
		}
	}

	virtual ~HierarchicalGridNode_Quad()
	{
		for(s32 i = 0; i < 4; ++i)
		{
			SAFE_DEL(nodes[i]);
		}
	}

	virtual s32 GetType() const
	{
		return HierarchicalGridNode<T,EmptyValue>::k_typeQuad;
	}

	virtual T Get(s32 x, s32 y) const
	{
		s32 i = (x < m_sx0) ? 0 : 1;
		s32 j = (y < m_sy0) ? 0 : 1;
		HierarchicalGridNode<T,EmptyValue>* node = nodes[j*2 + i];
		if (!node)
		{
			return EmptyValue;
		}
		x = x - i * m_sx0;
		y = y - j * m_sy0;
		return node->Get(x,y);
	}

	HierarchicalGridNode_Quad(DataStream& stream) :
		HierarchicalGridNode<T,EmptyValue>(),
		m_sx0(-1),
		m_sy0(-1)
	{
		m_sx0 = stream.ReadShort();
		m_sy0 = stream.ReadShort();
		for(s32 i = 0; i < 4; ++i)
		{
			s8 type = stream.ReadByte();
			if (type == HierarchicalGridNode<T,EmptyValue>::k_typeNull)
			{
				nodes[i] = 0;
			}
			else if (type == HierarchicalGridNode<T,EmptyValue>::k_typeGrid)
			{
				nodes[i] = NEW HierarchicalGridNode_Grid<T,EmptyValue>(stream);
			}
			else if (type == HierarchicalGridNode<T,EmptyValue>::k_typeQuad)
			{
				nodes[i] = NEW HierarchicalGridNode_Quad<T,EmptyValue>(stream);
			}
			else
			{
				ASSERT(false);
			}
		}
	}
		
	virtual void Export(DataStream& stream) const
	{
		stream.WriteShort(m_sx0);
		stream.WriteShort(m_sy0);
		for(s32 i = 0; i < 4; ++i)
		{
			s8 type = nodes[i] ? nodes[i]->GetType() : HierarchicalGridNode<T,EmptyValue>::k_typeNull;
			stream.WriteByte(type);
			if (type == HierarchicalGridNode<T,EmptyValue>::k_typeNull)
			{
				ASSERT(nodes[i] == 0);
			}
			else
			{
				nodes[i]->Export(stream);
			}
		}
	}

	static EScanResult ScanNode(T* data, s32 stride, s32 sx, s32 sy)
	{
		s32 countEmpty = 0;
		s32 countFull = 0;
		for (s32 y = 0; y < sy; ++y)
		{
			for (s32 x = 0; x < sx; ++x)
			{
				if (data[y*stride + x] != EmptyValue)
				{
					++countFull;
				}
				else
				{
					++countEmpty;
				}
			}
		}
		if (countFull == 0)
		{
			return k_empty;
		}
		s32 count = countFull + countEmpty;
		s32 mixedSize = countFull * sizeof(T) + 4 * sizeof(HierarchicalGridNode_Grid<T,EmptyValue>) + sizeof(HierarchicalGridNode_Quad<T,EmptyValue>);
		s32 fullSize = count * sizeof(T);
		if (fullSize < mixedSize)
		{
			return k_full;
		}
		return k_mixed;
	}

	static HierarchicalGridNode<T,EmptyValue>* CreateNode(T* data, s32 stride, s32 sx, s32 sy)
	{
		EScanResult scan = ScanNode(data, stride, sx, sy);
		if (scan == k_mixed)
		{
			return NEW HierarchicalGridNode_Quad<T,EmptyValue>(data, stride, sx, sy);
		}
		else if (scan == k_full)
		{
			return NEW HierarchicalGridNode_Grid<T,EmptyValue>(data, stride, sx, sy);
		}
		ASSERT(scan == k_empty);
		return 0;
	}

	s16 m_sx0;
	s16 m_sy0;
	HierarchicalGridNode<T,EmptyValue>* nodes[4];
};

template<typename T, T EmptyValue>
class HGrid : public HierarchicalGridNode_Quad<T,EmptyValue>
{
public:
	HGrid(T* data, s32 stride, s32 sx, s32 sy) :
		HierarchicalGridNode_Quad<T,EmptyValue>(data, stride, sx, sy)
	{
	}

	HGrid(DataStream& stream) :
		HierarchicalGridNode_Quad<T,EmptyValue>(stream)
	{
	}
};

#endif
